package recursive

import (
	"fmt"
	"strconv"
)

func printNums(n int) {
	if n > 2 {
		printNums(n - 1)
	}
	fmt.Println("n = " + strconv.Itoa(n))
}

// 递归实现
func fibonacci(n int) int {
	if n == 1 || n == 2 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

// 动态规划
func fibonacciV2(n int) int {
	if n <= 2 {
		return 1
	}
	result := make([]int, n)
	result[0], result[1] = 1, 1

	for i := 2; i < n; i++ {
		result[i] = result[i-1] + result[i-2]
	}

	return result[n-1]
}
